#define _CRT_SECURE_NO_WARNINGS


#pragma once
#include<vector>
#include<string>
#include<assert.h>
using namespace std;

namespace myhash
{
	template<class V>
	struct Node
	{
		V _data;

		Node<V>* _next;

		Node(const V& data = V())
			:_data(data)
			, _next(nullptr)
		{}
	};

	template<class V,class R,class P, class Hash,class KeyOfV>
	struct HashIterator
	{
		typedef Node<V> Node;

		Node* _node;
		const vector<Node*>& _table;

		HashIterator(Node* node,const vector<Node*>& table)
			:_node(node)
			,_table(table)
		{}

		HashIterator operator++()
		{
			assert(_node != nullptr);

			if (_node->_next)
			{
				_node = _node->_next;
			}
			else
			{
				KeyOfV kov;
				Hash ha;
				size_t keyi = ha(kov(_node->_data)) % _table.size();
				bool flag = true;
				for (int i = keyi + 1; i < _table.size(); i++)
				{
					if (_table[i] != nullptr)
					{
						_node = _table[i];
						flag = false;
						break;
					}
				}
				if (flag)
					_node = nullptr;
			}
			return *this;
		}
		HashIterator operator++(int)
		{
			HashIterator tmp = *this;
			this->operator++();
			return tmp;
		}
		HashIterator operator--()
		{
			if (_node == nullptr)
			{
				for (int i = _table.size()-1; i >= 0; i--)
				{
					if (_table[i] != nullptr)
					{
						Node* tmp = _table[i];
						while (tmp->_next)
						{
							tmp = tmp->_next;
						}
						_node = tmp;
						break;
					}
				}
				return *this;
			}


			KeyOfV kov;
			Hash ha;
			size_t keyi = ha(kov(_node->_data)) % _table.size();

			Node* cur = _table[keyi];
			Node* prev = nullptr;
			bool flag = false;
			while (cur)
			{
				if (cur == _node)
				{
					break;
				}
				prev = cur;
				cur = cur->_next;
			}
			if (prev == nullptr)
			{
				for (int i = keyi - 1; i >=0; i--)
				{
					if (_table[i] != nullptr)
					{
						flag = true;
						Node* tmp = _table[i];
						while (tmp->_next)
						{
							tmp = tmp->_next;
						}
						_node = tmp;
						break;
					}
				}
			}
			else
			{
				flag = true;
				_node = prev;
			}

			assert(flag);
			return *this;
		}
		HashIterator operator--(int)
		{
			HashIterator tmp = *this;
			this->operator--();
			return tmp;
		}
		bool operator==(const HashIterator& obj)const
		{
			return _node == obj._node;
		}
		bool operator!=(const HashIterator& obj)const
		{
			return _node != obj._node;
		}
		R operator*()const
		{
			return _node->_data;
		}
		P operator->()const
		{
			return &(_node->_data);
		}
	};

	template<class K, class V, class Hash, class Pred ,class KeyOfV>
	class hash
	{
		typedef Node<V> Node;
	public:
		typedef HashIterator<V, V&, V*, Hash, KeyOfV> Iterator;
		typedef HashIterator<V, const V&, const V*, Hash, KeyOfV> ConstIterator;

		hash(const size_t size = 13)
		{
			_hash.resize(size, nullptr);
			_size = 0;
		}
		hash(const hash& obj)
		{
			_hash.resize(obj._hash.size());
			_size = obj._size;
			for (int i = 0; i < obj._hash.size(); i++)
			{
				if (obj._hash[i])
				{
					Node* cur = obj._hash[i];
					Node* prev = nullptr;
					while (cur)
					{
						Node* newnode = new Node(cur->_data);
						if (prev)
							prev->_next = newnode;
						prev = newnode;
						cur = cur->_next;
						if (_hash[i] == nullptr)
							_hash[i] = newnode;
					}
				}
			}
		}
		hash& operator=(hash obj)
		{
			swap(obj);
			return *this;
		}
		~hash()
		{
			for (int i = 0; i < _hash.size(); i++)
			{
				if (_hash[i])
				{
					Node* cur = _hash[i];
					while (cur)
					{
						Node* next = cur->_next;
						delete cur;
						cur = next;
					}
					_hash[i] = nullptr;
				}
			}
		}
		void swap(hash& obj)
		{
			_hash.swap(obj._hash);
			std::swap(_size, obj._size);
		}

		Iterator begin()
		{
			if (_size == 0)
				return end();
			for (int i = 0; i < _hash.size(); i++)
			{
				if (_hash[i])
					return Iterator(_hash[i], _hash);
			}

			return end();
		}
		Iterator end()
		{
			return Iterator(nullptr,_hash);
		}
		ConstIterator begin()const
		{
			if (_size == 0)
				return end();
			for (int i = 0; i < _hash.size(); i++)
			{
				if (_hash[i])
					return ConstIterator(_hash[i], _hash);
			}
			return end();
		}
		ConstIterator end()const
		{
			return ConstIterator(nullptr, _hash);
		}
		void reserve(size_t n)
		{
			if (n <= _hash.size())
				return;

			hash tmp(n);

			for (int i = 0; i < _hash.size(); i++)
			{
				KeyOfV kov;
				if (_hash[i])
				{
					Node* cur = _hash[i];
					while (cur)
					{
						Hash ha;
						size_t keyi = ha(kov(cur->_data)) % (tmp._hash.size());

						tmp._size++;

						Node* next = cur->_next;

						cur->_next = tmp._hash[keyi];
						tmp._hash[keyi] = cur;

						cur = next;
					}
					_hash[i] = nullptr;
				}
			}
			swap(tmp);
		}
		pair<Iterator,bool> insert(const V& data)
		{
			KeyOfV kov;
			if (find(kov(data)) !=end())
				return make_pair(find(kov(data)),false);

			double load = (double)_size / _hash.size();

			if (load >= 1.0)
			{
				reserve(_hash.size() * 2.5);
			}

			Hash ha;
			size_t keyi = ha(kov(data)) % (_hash.size());

			Node* newnode = new Node(data);

			newnode->_next = _hash[keyi];
			_hash[keyi] = newnode;


			_size++;

			return make_pair(Iterator(newnode,_hash), true);
		}
		bool erase(const K& key)
		{
			Hash ha;
			size_t keyi = ha(key) % (_hash.size());
			Pred pred;
			Node* cur = _hash[keyi];
			Node* prev = nullptr;
			KeyOfV kov;
			while (cur)
			{
				if (pred(kov(cur->_data), key))
				{
					if (prev == nullptr)
					{
						_hash[keyi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					_size--;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}
		Iterator find(const K& key)
		{
			Hash ha;
			KeyOfV kov;
			size_t keyi = ha(key) % (_hash.size());
			Pred pred;
			Node* cur = _hash[keyi];
			while (cur)
			{
				if (pred(kov(cur->_data), key))
				{
					return Iterator(cur,_hash);
				}
				cur = cur->_next;
			}
			return end();
		}
		ConstIterator find(const K& key)const
		{
			Hash ha;
			KeyOfV kov;
			size_t keyi = ha(key) % (_hash.size());
			Pred pred;
			Node* cur = _hash[keyi];
			while (cur)
			{
				if (pred(kov(cur->_data), key))
				{
					return ConstIterator(cur, _hash);
				}
				cur = cur->_next;
			}
			return end();
		}
		bool empty()const
		{
			return _size == 0;
		}
		size_t size()const
		{
			return _size;
		}
	private:
		vector<Node*>_hash;
		size_t _size;
	};
}